package _2022.hot100._309_最佳买卖股票时机含冷冻期;

/**
 * @author： YHSimon
 * @date： 2022-05-27 10:25
 */
public class Solution {
    // 1ms
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
        }
        return Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2]));
    }

    //空间优化 0ms
    public int maxProfit2(int[] prices) {
        if (prices.length == 0) return 0;
        int n = prices.length;
        int f0 = -prices[0], f1 = 0, f2 = 0;
        for (int i = 1; i < n; i++) {
            int newf0 = Math.max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = Math.max(f1, f2);
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }
        return Math.max(f0, Math.max(f1, f2));
    }
}
